package org.basis.algorithm.sort;

import org.basis.algorithm.sort.common.SortUtil;

import java.util.Arrays;

/**
 * 归并排序
 *
 * @author Mr_wenpan@163.com 2022/01/26 16:10
 */
public class MergeSort {

    public static void main(String[] args) {

        final int num = 10000;
        for (int i = 0; i < num; i++) {
            int[] arr = SortUtil.generateRandomArray(100, 100);
            int[] copyArray = SortUtil.copyArray(arr);
            Arrays.sort(copyArray);
            mergeSort(arr);
            if (!SortUtil.isEqual(arr, copyArray)) {
                System.out.println("fuck!");
                break;
            }
        }
    }

    public static void mergeSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        doMergeSort(arr, 0, arr.length - 1);
    }

    public static void doMergeSort(int[] arr, int left, int right) {
        // base case
        if (left >= right) {
            return;
        }
        // 防止溢出
        int mid = left + (right - left) / 2;

        // 一直往下将区间二分缩小
        doMergeSort(arr, left, mid);
        doMergeSort(arr, mid + 1, right);

        // merge
        int[] help = new int[right - left + 1];
        int l = left;
        int r = mid + 1;
        int index = 0;

        // 左右指针都不越界的情况下，谁小拷贝谁
        while (l <= mid && r <= right) {
            if (arr[l] < arr[r]) {
                help[index++] = arr[l];
                l++;
            } else {
                help[index++] = arr[r];
                r++;
            }
        }

        // 谁先越界就拷贝另一个
        while (l <= mid) {
            help[index++] = arr[l];
            l++;
        }
        while (r <= right) {
            help[index++] = arr[r];
            r++;
        }

        // 从辅助数组从拷贝回原数组
        for (int i = 0; i < help.length; i++) {
            arr[left + i] = help[i];
        }
    }

}
